/* Nick Mancuso and Dinesh Agarwal */
/* Updated: 7 April 2010 */
/* single lock on entire heap, concurrent delete and inserts */
/* expInc */
/* node struct */
/*Update History */
/* Added Pardef.h - Sep 11, 2010 */

#include  <stdio.h>
#include  <stdlib.h>
#include  <math.h>
#include  <string.h>
#include  <sys/param.h>
#include  <malloc.h>
#include  <sched.h>
#include  <sys/time.h>
#include  <sys/times.h>
#include  <sys/types.h>
#include  <pthread.h>
#include "think.h"
#include "timer.h"
#include "pardef.h"
#include "exp_inc.h"

#define EMPTY 3276800
#define MAXLEVEL 23

struct    tms  tim ;
char      ch ;

typedef struct
{
    int key;             /* node priority i.e. time-stamp of message */
} node;

void* heap_process(void *);
void insertNoLocks(int key);
void insertSync(int key);
int delete1(int key);
extern int exp_inc();
int deleteNoLocks(int key);

node *heap;
pthread_mutex_t mut = PTHREAD_MUTEX_INITIALIZER;
int numprocessors, inserts, deletes, locksize, lastelem;
int MAX_THINK_TIME;
int CYCLES;

void print_heap()
{
    int i;

    for (i=1; i<=lastelem; i++)
    {
        printf(" %d ", heap[i].key);
        if (i%10 == 0) printf("\n");
    }
    printf("\n");
}

int main(int argc, char *argv[])
{
    int i, heapsize,  maxheapsize;
    pthread_t *threads;
    double StartTime, EndTime;

    if (argc != 7)
    {
        fprintf(stderr, "Usage : %s <numprocessors> <size of starting heap>\n", argv[0]);
        fprintf(stderr, "<deletes> <insert> <think time> <cycles>\n");
        exit(0) ;
    }

    /* Read Command line arguments */
    numprocessors   = atoi(argv[1]);
    heapsize        = atoi(argv[2]);
    deletes         = atoi(argv[3]);
    inserts         = atoi(argv[4]);
    MAX_THINK_TIME  = atoi(argv[5]);
    CYCLES          = atoi(argv[6]);

    /* Allocate memory for heap */
    maxheapsize = 2 * heapsize  ;
    heap = (node *) malloc ( maxheapsize * sizeof(node));

    threads = (pthread_t*) malloc(numprocessors * sizeof(pthread_t));

    /* Create heap using random values */
    lastelem =  0;
    for (i=1; i<=heapsize; i++)
    {
        insertNoLocks(rand() % MAX_ITEM_VALUE);
    }
    //print_heap();
    StartTime = my_difftime();


    for (i = 0; i < numprocessors; i++)
    {
        pthread_create(&threads[i], NULL, &heap_process, NULL);
    }

    for (i = 0; i < numprocessors; i++)
    {
        pthread_join(threads[i], NULL);
    }

    EndTime = my_difftime();
    double difference = EndTime - StartTime;

    printf("%f\t", difference);
    //print_heap();
    free(threads);
    free(heap);
    return EXIT_SUCCESS;
}


#ifdef RELAXED_HOLD
void* heap_process(void* p)
{
    int j, key=0, deletedkey = 0;
    int RelaxedHold;

    for (j=0; j < CYCLES * deletes; j++)
    {
        RelaxedHold = rand() % 3;
    
        if (RelaxedHold == 1)
        {
            key = exp_inc();
            deletedkey = delete1(key+deletedkey);
            think(MAX_THINK_TIME);
        }
        else if (RelaxedHold == 2)
        {
            key = exp_inc();
            deletedkey = delete1(key+deletedkey);
            think(MAX_THINK_TIME);
            key = exp_inc();
            insertSync(key);
        }
        else
        {
    
            delete1(-1);
            think(MAX_THINK_TIME);
        }
    }

    pthread_exit(NULL);
    return NULL;
}
#else
void* heap_process(void* p)
{
    int i,j, key=0, deletedkey = 0;

    int Combined_InsDel = 0;
    int ExtraIns = 0;
    int ExtraDel = 0;

    for (j=0; j < CYCLES; j++)
    {

        if ( inserts >= deletes )
        {
            Combined_InsDel = deletes;
            ExtraIns = inserts - deletes;
        }
        else
        {
            Combined_InsDel = inserts;
            ExtraDel = deletes - inserts;
        }
        /* Do the combined insertion and deletion */
        for ( i = 0; i < Combined_InsDel; i++)
        {
            key = exp_inc();
            deletedkey = delete1(key+deletedkey);
            think(MAX_THINK_TIME);
        }
    
        /* If there were less items to be inserted
         * then to be deleted, we need to delete some more
         * than those deleted above */
        for ( i = 0; i < ExtraDel; i++)
        {
            delete1(-1);
            think(MAX_THINK_TIME);
        }
    
        /* If there were more items to be inserted
         * then to be deleted, we need to insert some more
         * than those inserted above */
        for ( i = 0; i < ExtraIns; i++)
        {
            key += exp_inc();
            //printf("%d ",key); 
            insertSync(key);
        }
    }

    pthread_exit(NULL);
    return NULL;
}
#endif

int delete1(int key)
{
    int item, n, least, i, j;

    if (numprocessors > 1)
        pthread_mutex_lock(&mut);

    if (lastelem == 0)
    {
        if (numprocessors > 1)
            pthread_mutex_unlock(&mut);

        return key;
    }

    least = heap[1].key;

    /*  if key is -1, we just delete, otherwise
     *  we do an insert/delete combination  */
    if (key >= 0)
    {
        if (key <= least)
        {
            if (numprocessors > 1)
                pthread_mutex_unlock(&mut);
            return key;
        }
        else
        {
            heap[1].key = key;
        }
    }
    else
    {
        heap[1].key = heap[lastelem].key;
        lastelem--;
    }

    /* adjust heap */
    i=1;
    j = 2*i;
    item = heap[i].key;
    n = lastelem;
    while (j <= n)
    {
        if ((j<n) && (heap[j].key > heap[j+1].key))
            j++;
        if (item <= heap[j].key)
            break;
        else
        {
            heap[(int) j/2].key = heap[j].key;
            j = 2*j;
        }
    }
    heap[(int) j/2].key = item;

    if (numprocessors > 1)
        pthread_mutex_unlock(&mut);
    return least;
}

void insertSync(int key)
{
    if (numprocessors > 1)
    {
        pthread_mutex_lock(&mut);
    }

    insertNoLocks(key);

    if (numprocessors > 1)
    {
        pthread_mutex_unlock(&mut);
    }
}

void insertNoLocks(int key)
{
    int parent, current;

    /* increase last element for the current node to
     * insert, then get parent to heapify
     */
    ++lastelem;
    heap[lastelem].key = key;
    current = lastelem;
    parent = (int) current/2;

    /* heapify by swapping upward */
    while ((parent > 0) && (heap[parent].key > key))
    {
        heap[current].key = heap[parent].key;
        current = parent;
        parent = (int) parent/2;
    }

    heap[current].key = key;

}


void init(int events)
{
    int count, value;

    count = 0 ;
    value=0;
    while (count < events)
    {
        if (rand()%10 >=4)
        {
            value = value + exp_inc();
            insertNoLocks(value);
            ++count;
        }
        else
        {
            value = deleteNoLocks(-1);
            --count;
        }
    }
}

int deleteNoLocks(int key)
{
    int item, n, least, i, j;

    if (lastelem == 0)
    {
        return key;
    }

    least = heap[1].key;

    if (key >= 0)
    {
        if (key <= least)
        {
            return key ;
        }
        else
        {
            heap[1].key = key;
        }
    }
    else
    {
        heap[1].key = heap[lastelem].key;
        lastelem--;
    }

    /* adjust heap */
    i=1;
    j = 2*i;
    item = heap[i].key;
    n = lastelem;
    while (j <= n)
    {
        if ((j<n) && (heap[j].key > heap[j+1].key))
            j++;
        if (item <= heap[j].key)
            break;
        else
        {
            heap[(int) j/2].key = heap[j].key;
            j = 2*j;
        }
    }
    heap[(int) j/2].key = item;
    return least;
};
